This site is supported by donations to The OEIS Foundation.
Complete non-self-adjacent paths:Program
From OeisWiki
/*
Filename: CNSAP.cpp
Purpose: To calculate all complete non-self-adjacent paths (CNSAPs) in square and cubic lattices bounded by various sizes of rectangle and
rectangular cuboid respectively.
Build info: The program builds as a console project using Microsoft Visual C++ Express Edition and requires the header file stdafx.h contains the header files:
#include <iomanip>
#include <iostream>
#include <fstream>
Development history:
Initially developed by Tom Young in July and August 2010.
Subsequently developed by Chris Gribble.
*/
#include "stdafx.h"
using namespace System;
using namespace std;
const int maxDirections = 6; /* Maximum number of directions in which path progression can take place from a node. */
const int maxLengths = 343; /* Maximum number of distinct CNSAP lengths allowed. */
const int maxNodes = 343; /* Maximum number of nodes allowed in the bounded lattice. */
const int maxNeighborsPlus3 = 9; /* Maximum number of neighbors a node can have (6) plus 3 */
const int maxShapes = 5000000; /* Maximum number of distinct CNSAP shapes allowed. */
long long i_ll; /* Loop counter. */
long long numberOfPathsPerLength[maxLengths]; /* Number of paths of each length. */
long long numberOfShapesPerLength[maxLengths]; /* Number of distinct path shapes of each length. */
long long endNodePerLength[maxNodes][maxLengths]; /* Number of paths of each length for each ending node. */
long long pathNodePerLength[maxNodes][maxLengths]; /* Number of paths of each length for each path node. */
long long startNodePerLength[maxNodes][maxLengths]; /* Number of paths of each length for each starting node. */
long long endNode[maxNodes]; /* Number of paths for each ending node. */
long long pathNode[maxNodes]; /* Number of paths for each path node. */
long long startNode[maxNodes]; /* Number of paths for each starting node. */
long long startEndNode[maxNodes][maxNodes]; /* Number of paths for each starting-ending node pair. */
long long totalNumberOfPaths; /* Total number of paths. */
long long totalNumberOfShapes; /* Total number of distinct path shapes. */
int currentPath[maxNodes]; /* Sequence of nodes in the current path under construction. */
int nodeNeighbors[maxNodes][maxNeighborsPlus3]; /* Create the node neighbor array: */
/* Column 0 is unused and is an artifact from the translation from Liberty Basic to C++. */
/* Column 1 holds the number of neighbors. */
/* Columns 2 to 7 hold the neighbor node values. */
/* Column 8 holds the value -1. */
/*
int numberOfPathsPerShape[maxShapes]; /* Number of paths with each distinct shape.
*/
int unusableNodes[maxNodes][maxNeighborsPlus3]; /* As a path is created, the starting node and unused neighbors of path nodes are recorded */
/* as unavailable for future use within it. */
int unusedNodes[maxNodes][maxNeighborsPlus3]; /* Records the unused neighbors of each node taken over all CNSAPs constructed. */
/* When a path cannot be made any longer we backtrack and make use of the first */
/* available unused node neighbor to construct a new path. */
int a, b, c; /* Dimensions of lattice boundary in x , y and z directions, respectively. */
int i, j, k, m, n; /* Loop counters. */
int candidateNextNode; /* Candidate for the next node in the path. */
int currentNode; /* The current node at the end of the path under construction. */
int currentNodePointer; /* Points to the current node in the path under construction. */
int firstNode; /* User-specified first node in all CNSAPs. */
int latticeDimension; /* User-specified lattice dimension (2 or 3). */
int longestCNSAP; /* Length of current longest CNSAP for path display control. */
int matchCount; /* Count of those neighbors of firstNode that do not match secondNode. */
int minPathLength, maxPathLength, pathLength; /* Minimum, maximum and current CNSAP lengths. */
int nextNeighborPointer; /* Points to the next node neighbor. */
int nextUnusableNodePointer; /* Points to the next unusable node slot. */
int numberOfNodes; /* Number of nodes in the bounded lattice. */
int numberOfSecondNodes; /* User-specified number of second nodes. */
int secondNode; /* User-specified second node. */
bool addNode; /* Indicates whether candidateNextNode can be added to the path under construction or not. */
bool anyUnusedNodes; /* Indicates whether there are any unused nodes left for path building or not. */
bool finished; /* Indicates whether the program run is finished or not. */
bool noNextNode; /* Indicates whether a path can be extended or not. If not, it is a CNSAP. */
bool shapeMatch; /* Indicates whether the shape of the current CNSAP has already been recorded or not. */
bool unusable; /* Indicates whether a node is recorded as unusable or not. */
char currentPathDirections[maxNodes]; /* Sequence of direction indicators corresponding to the current path. */
char distinctPathShapes[maxShapes][maxNodes]; /* Set of distinct CNSAP shapes generated. */
char nodeNeighborDirections[maxNodes][maxDirections]; /* Indicates direction of each neighbor from each node: */
/* r = right (+x), l = left (-x), u = up (+y), d = down (-y), a = above (+z), b = below (-z)*/
char rotatedPathDirections[maxNodes]; /* Equivalent of currentPathDirections, suitably rotated. */
char allStartNodes; /* User requirement to generate paths starting with each node or one particular node (Y or N). */
char outputAllPaths; /* User requirement to output all paths (Y or N). */
char outputShapeStats; /* User requirement to output path shape statistics. */
char specifySecondNodes; /* User requirement to specify one or more second nodes (Y or N). */
int main ()
{
/*
This program determines the set of all complete non-adjacent paths (CNSAPs) in a square lattice bounded by a rectangle or a cubic lattice
bounded by a rectangular cuboid.
In particular, it determines their lengths and shapes independent of rotation.
In the 2D mode, the user is prompted to supply the dimensions of the rectangle, a and b.
In the 3D mode, the user is prompted to supply the dimensions of the rectangular cuboid, a, b and c.
The user can either choose to generate all paths from all nodes in the lattice or all paths from a user-specified pair of starting nodes.
The first part of the program determines the set of neighbors for each node in the relevant lattice.
The node numbering convention for a selection of 2D lattices is:
a = b = 2 0 1
2 3
a = 2, b = 3 0 1
2 3
4 5
a = 3, b = 2 0 1 2
3 4 5
a = b = 3 0 1 2
3 4 5
6 7 8
a = b = 4 0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
a = b = 5 0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
Direction naming convention:
In a = b = 2, Node 0 is Left of node 1 and Up from Node 2
Node 3 is Right of Node 2 and Down from Node 1
The node numbering convention for a selection of 3D lattices is:
a = b = c = 2 0 1
2 3
4 5
6 7
a = b = c = 3 0 1 2
3 4 5
6 7 8
9 10 11
12 13 14
15 16 17
18 19 20
21 22 23
24 25 26
a = b = c = 4 0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19
20 21 22 23
24 25 26 27
28 29 30 31
32 33 34 35
36 37 38 39
40 41 42 43
44 45 46 47
48 49 50 51
52 53 54 55
56 57 58 59
60 61 62 63
Direction naming convention:
In a = b = c = 2, Node 0 is Left of node 1, Up from Node 2 and Above Node 4
Node 7 is Right of Node 6 and Down from Node 5 and Below Node 3
*/
/* Create output file. */
fstream file;
file.open("CNSAP.txt", ios_base::out | ios_base::trunc);
/* Initialise variables. */
longestCNSAP = 0; /* Set the longest path encountered so far to zero. */
totalNumberOfShapes = 0; /* Set the number of distinct path shapes encountered to zero. */
for (i = 0; i < maxNodes; i++)
numberOfShapesPerLength[i] = 0;
/* Get lattice type. */
cout << "Enter dimension of lattice [2 = 2D / 3 = 3D] ";
cin >> latticeDimension;
if (latticeDimension != 2 && latticeDimension != 3)
goto error;
if (latticeDimension == 2)
{
/* Get dimensions of lattice. */
cout << "Enter length of rectangle > 1, a = "; /* Get the length dimension a a a a */
cin >> a;
if (a < 2)
goto error;
cout << "Enter width of rectangle > 1, b = "; /* Get the width dimension b */
cin >> b; /* b */
/* b */
/* b */
if (b < 2)
goto error;
numberOfNodes = a * b;
if (numberOfNodes > maxNodes)
goto error;
file << "Lattice has 2 dimensions" << endl;
file << "Length of rectangle, a = " << a << endl;
file << "Width of rectangle, b = " << b << endl;
/* Initialise minimum and maximum path lengths. */
minPathLength = numberOfNodes;
maxPathLength = 0;
/* The first part of the program creates the neighbor array. This part of the program has 3 parts. */
/* Make sure the array is clean. */
for (i = 0; i < numberOfNodes; i++)
{
for (k = 1; k < maxNeighborsPlus3; k++)
{
nodeNeighbors[i][k] = 0;
}
for (k = 0; k < maxDirections; k++)
{
nodeNeighborDirections[i][k] = ' ';
}
}
/* Part one identifies the corner points of the lattice, each of which has 2 neighbors, */
/* and identifies them. */
/* Part One */
/* Top left hand corner. */
n = 0;
nodeNeighbors[n][1] = 2;
nodeNeighbors[n][2] = 1;
nodeNeighbors[n][3] = a;
nodeNeighborDirections[n][0] = 'r'; /* Node 1 is one step right from node 0. */
nodeNeighborDirections[n][1] = 'd'; /* Node a is one step down from node 0. */
/* Top right hand corner. */
n = a - 1;
nodeNeighbors[n][1] = 2;
nodeNeighbors[n][2] = a - 2;
nodeNeighbors[n][3] = 2 * a - 1;
nodeNeighborDirections[n][0] = 'l'; /* Node (a - 2) is one step left from node (a - 1). */
nodeNeighborDirections[n][1] = 'd'; /* Node (2a - 1) is one step down from node (a - 1). */
/* Bottom left hand corner. */
n = a * b - a;
nodeNeighbors[n][1] = 2;
nodeNeighbors[n][2] = a * b - 2 * a;
nodeNeighbors[n][3] = a * b - a + 1;
nodeNeighborDirections[n][0] = 'u'; /* Node (ab - 2a) is one step up from node (ab - a). */
nodeNeighborDirections[n][1] = 'r'; /* Node (ab - a + 1) is one step right from node (ab - a). */
/* Bottom right hand corner. */
n = a * b - 1;
nodeNeighbors[n][1] = 2;
nodeNeighbors[n][2] = a * b - a - 1;
nodeNeighbors[n][3] = a * b - 2;
nodeNeighborDirections[n][0] = 'u'; /* Node (ab - a - 1) is one step up from node (ab - 1). */
nodeNeighborDirections[n][1] = 'l'; /* Node (ab - 2) is one step left from node (ab - 1). */
/* Part Two figures out the lattice points that have 3 neighbors. */
/* These points reside along the 4 edges of the rectangle and are not corner points. */
/* Part Two */
/* Edges in the length [a] direction. This will not be done if a = 2 since there are no edge nodes then. */
if (a > 2)
{
/* Top edge. */
for (i = 1; i <= a - 2; i++)
{
nodeNeighbors[i][1] = 3;
nodeNeighbors[i][2] = i - 1;
nodeNeighbors[i][3] = i + 1;
nodeNeighbors[i][4] = i + a;
nodeNeighborDirections[i][0] = 'l'; /* Node i - 1 is one step left from node i. */
nodeNeighborDirections[i][1] = 'r'; /* Node i + 1 is one step right from node i. */
nodeNeighborDirections[i][2] = 'd'; /* Node i + a is one step down from node i. */
}
/* Bottom edge. */
for (i = a * b - a + 1; i <= a * b - 2; i++)
{
nodeNeighbors[i][1] = 3;
nodeNeighbors[i][2] = i - a;
nodeNeighbors[i][3] = i - 1;
nodeNeighbors[i][4] = i + 1;
nodeNeighborDirections[i][0] = 'u'; /* Node i - a is one step up from node i. */
nodeNeighborDirections[i][1] = 'l'; /* Node i - 1 is one step left from node i. */
nodeNeighborDirections[i][2] = 'r'; /* Node i + 1 is one step right from node i. */
}
}
/* Edges in the length [b] direction. */
if (b > 2)
{
/* Left hand edge. */
for (i = a; i <= a * b - 2 * a; i += a)
{
nodeNeighbors[i][1] = 3;
nodeNeighbors[i][2] = i - a;
nodeNeighbors[i][3] = i + 1;
nodeNeighbors[i][4] = i + a;
nodeNeighborDirections[i][0] = 'u'; /* Node i - a is one step up from node i. */
nodeNeighborDirections[i][1] = 'r'; /* Node i + 1 is one step right from node i. */
nodeNeighborDirections[i][2] = 'd'; /* Node i + a is one step down from node i. */
}
/* Right hand edge. */
for (i = 2 * a - 1; i <= a * b - a - 1; i += a)
{
nodeNeighbors[i][1] = 3;
nodeNeighbors[i][2] = i - a;
nodeNeighbors[i][3] = i - 1;
nodeNeighbors[i][4] = i + a;
nodeNeighborDirections[i][0] = 'u'; /* Node i - a is one step up from node i. */
nodeNeighborDirections[i][1] = 'l'; /* Node i - 1 is one step left from node i. */
nodeNeighborDirections[i][2] = 'd'; /* Node i + a is one step down from node i. */
}
}
/* Part Three identifies the lattice points that have 4 neighbors. */
/* These points all lie within the rectangle. */
/* Part Three */
for (i = 0; i < numberOfNodes; i++)
{
if (nodeNeighbors[i][1] == 0)
{
nodeNeighbors[i][1] = 4;
nodeNeighbors[i][2] = i - a;
nodeNeighbors[i][3] = i - 1;
nodeNeighbors[i][4] = i + 1;
nodeNeighbors[i][5] = i + a;
nodeNeighborDirections[i][0] = 'u'; /* Node i - a is one step up from node i. */
nodeNeighborDirections[i][1] = 'l'; /* Node i - 1 is one step left from node i. */
nodeNeighborDirections[i][2] = 'r'; /* Node i + 1 is one step right from node i. */
nodeNeighborDirections[i][3] = 'd'; /* Node i + a is one step down from node i. */
}
}
}
else if (latticeDimension == 3)
{
/* Get dimensions of lattice. */
cout << "Enter length of cuboid, a = "; /* Get the length dimension a a a a */
cin >> a;
if (a < 2)
goto error;
cout << "Enter width of cuboid, b = "; /* Get the width dimension b */
cin >> b; /* b */
/* b */
/* b */
if (b < 2)
goto error;
cout << "Enter height of cuboid, c = "; /* Get the height dimension c */
cin >> c; /* c */
/* c */
/* c */
if (c < 2)
goto error;
numberOfNodes = a * b * c;
if (numberOfNodes > maxNodes)
goto error;
file << "Lattice has 3 dimensions" << endl;
file << "Length of cuboid, a = " << a << endl;
file << "Width of cuboid, b = " << b << endl;
file << "Height of cuboid, c = " << c << endl;
/* Initialise minimum and maximum path lengths. */
minPathLength = numberOfNodes;
maxPathLength = 0;
/* The first part of the program creates the neighbor array. This part of the program has 4 parts. */
/* Make sure the array is clean. */
for (i = 0; i < numberOfNodes; i++)
{
for (k = 1; k < maxNeighborsPlus3; k++)
{
nodeNeighbors[i][k] = 0;
}
}
/* Part one finds the corner points of the lattice and assigns them the number 3 since they have three neighbors. */
/* Then, for each corner, it figures out the neighbors. */
/* Part One */
/* Upper face, top left hand corner. */
n = 0;
nodeNeighbors[n][1] = 3;
nodeNeighbors[n][2] = n + 1;
nodeNeighbors[n][3] = n + a;
nodeNeighbors[n][4] = n + a * b;
nodeNeighborDirections[n][0] = 'r'; /* Node n + 1 is one step right from node n. */
nodeNeighborDirections[n][1] = 'd'; /* Node n + a is one step down from node n. */
nodeNeighborDirections[n][2] = 'b'; /* Node n + ab is one step below node n. */
/* Upper face, top right hand corner. */
n = a - 1;
nodeNeighbors[n][1] = 3;
nodeNeighbors[n][2] = n - 1;
nodeNeighbors[n][3] = n + a;
nodeNeighbors[n][4] = n + a * b;
nodeNeighborDirections[n][0] = 'l'; /* Node n - 1 is one step left from node n. */
nodeNeighborDirections[n][1] = 'd'; /* Node n - a is one step down from node n. */
nodeNeighborDirections[n][2] = 'b'; /* Node n + ab is one step below node n. */
/* Upper face, bottom left hand corner. */
n = a * b - a;
nodeNeighbors[n][1] = 3;
nodeNeighbors[n][2] = n - a;
nodeNeighbors[n][3] = n + 1;
nodeNeighbors[n][4] = n + a * b;
nodeNeighborDirections[n][0] = 'u'; /* Node n - a is one step up from node n. */
nodeNeighborDirections[n][1] = 'r'; /* Node n + 1 is one step right from node n. */
nodeNeighborDirections[n][2] = 'b'; /* Node n + ab is one step below node n. */
/* Upper face, bottom right hand corner. */
n = a * b - 1;
nodeNeighbors[n][1] = 3;
nodeNeighbors[n][2] = n - a;
nodeNeighbors[n][3] = n - 1;
nodeNeighbors[n][4] = n + a * b;
nodeNeighborDirections[n][0] = 'u'; /* Node n - a is one step up from node n. */
nodeNeighborDirections[n][1] = 'l'; /* Node n - 1 is one step left from node n. */
nodeNeighborDirections[n][2] = 'b'; /* Node n + ab is one step below node n. */
/* Lower face, top left hand corner. */
n = a * b * c - a * b;
nodeNeighbors[n][1] = 3;
nodeNeighbors[n][2] = n - a * b;
nodeNeighbors[n][3] = n + 1;
nodeNeighbors[n][4] = n + a;
nodeNeighborDirections[n][0] = 'a'; /* Node n - ab is one step above node n. */
nodeNeighborDirections[n][1] = 'r'; /* Node n + 1 is one step right from node n. */
nodeNeighborDirections[n][2] = 'd'; /* Node n + a is one step down from node n. */
/* Lower face, top right hand corner. */
n = a * b * c - a * b + a - 1;
nodeNeighbors[n][1] = 3;
nodeNeighbors[n][2] = n - a * b;
nodeNeighbors[n][3] = n - 1;
nodeNeighbors[n][4] = n + a;
nodeNeighborDirections[n][0] = 'a'; /* Node n - ab is one step above node n. */
nodeNeighborDirections[n][1] = 'l'; /* Node n - 1 is one step left from node n. */
nodeNeighborDirections[n][2] = 'd'; /* Node n + a is one step down from node n. */
/* Lower face, bottom left hand corner. */
n = a * b * c - a;
nodeNeighbors[n][1] = 3;
nodeNeighbors[n][2] = n - a * b;
nodeNeighbors[n][3] = n - a;
nodeNeighbors[n][4] = n + 1;
nodeNeighborDirections[n][0] = 'a'; /* Node n - ab is one step above node n. */
nodeNeighborDirections[n][1] = 'u'; /* Node n - a is one step up from node n. */
nodeNeighborDirections[n][2] = 'r'; /* Node n + 1 is one step right from node n. */
/* Lower face, bottom right hand corner. */
n = a * b * c - 1;
nodeNeighbors[n][1] = 3;
nodeNeighbors[n][2] = n - a * b;
nodeNeighbors[n][3] = n - a;
nodeNeighbors[n][4] = n - 1;
nodeNeighborDirections[n][0] = 'a'; /* Node n - ab is one step above node n. */
nodeNeighborDirections[n][1] = 'u'; /* Node n - a is one step up from node n. */
nodeNeighborDirections[n][2] = 'l'; /* Node n - 1 is one step left from node n. */
/* Part Two figures out the lattice points that have 4 neighbors. */
/* These points reside along the edges of the cube. */
/* Since there are twelve edges, we need twelve loops. */
/*Part Two*/
/*Top and bottom face edges in the length [a] direction. This will not be done if a = 2 since there are no edge nodes then. */
if (a > 2)
{
for (i = 1; i <= a - 2; i++)
{
nodeNeighbors[i][1] = 4;
nodeNeighbors[i][2] = i - 1;
nodeNeighbors[i][3] = i + 1;
nodeNeighbors[i][4] = i + a;
nodeNeighbors[i][5] = i + a * b;
nodeNeighborDirections[i][0] = 'l'; /* Node i - 1 is one step left from node i. */
nodeNeighborDirections[i][1] = 'r'; /* Node i + 1 is one step right from node i. */
nodeNeighborDirections[i][2] = 'd'; /* Node i + a is one step down from node i. */
nodeNeighborDirections[i][3] = 'b'; /* Node i + ab is one step below node i. */
}
for (i = a * b - a + 1; i <= a * b - 2; i++)
{
nodeNeighbors[i][1] = 4;
nodeNeighbors[i][2] = i - a;
nodeNeighbors[i][3] = i - 1;
nodeNeighbors[i][4] = i + 1;
nodeNeighbors[i][5] = i + a * b;
nodeNeighborDirections[i][0] = 'u'; /* Node i - a is one step up from node i. */
nodeNeighborDirections[i][1] = 'l'; /* Node i - 1 is one step left from node i. */
nodeNeighborDirections[i][2] = 'r'; /* Node i + 1 is one step right from node i. */
nodeNeighborDirections[i][3] = 'b'; /* Node i + ab is one step below node i. */
}
for (i = a * b * c - a * b + 1; i <= a * b * c - a * b + a - 2; i++)
{
nodeNeighbors[i][1] = 4;
nodeNeighbors[i][2] = i - a * b;
nodeNeighbors[i][3] = i - 1;
nodeNeighbors[i][4] = i + 1;
nodeNeighbors[i][5] = i + a;
nodeNeighborDirections[i][0] = 'a'; /* Node i - ab is one step above node i. */
nodeNeighborDirections[i][1] = 'l'; /* Node i - 1 is one step left from node i. */
nodeNeighborDirections[i][2] = 'r'; /* Node i + 1 is one step right from node i. */
nodeNeighborDirections[i][3] = 'd'; /* Node i + a is one step down from node i. */
}
for (i = a * b * c - a + 1; i <= a * b * c - 2; i++)
{
nodeNeighbors[i][1] = 4;
nodeNeighbors[i][2] = i - a * b;
nodeNeighbors[i][3] = i - a;
nodeNeighbors[i][4] = i - 1;
nodeNeighbors[i][5] = i + 1;
nodeNeighborDirections[i][0] = 'a'; /* Node i - ab is one step above node i. */
nodeNeighborDirections[i][1] = 'u'; /* Node i - a is one step up from node i. */
nodeNeighborDirections[i][2] = 'l'; /* Node i - 1 is one step left from node i. */
nodeNeighborDirections[i][3] = 'r'; /* Node i + 1 is one step right from node i. */
}
}
/* Top and bottom face edges in the length [b] direction. */
if (b > 2)
{
for (i = a; i <= a * b - 2 * a; i += a)
{
nodeNeighbors[i][1] = 4;
nodeNeighbors[i][2] = i - a;
nodeNeighbors[i][3] = i + 1;
nodeNeighbors[i][4] = i + a;
nodeNeighbors[i][5] = i + a * b;
nodeNeighborDirections[i][0] = 'u'; /* Node i - a is one step up from node i. */
nodeNeighborDirections[i][1] = 'r'; /* Node i + 1 is one step right from node i. */
nodeNeighborDirections[i][2] = 'd'; /* Node i + a is one step down from node i. */
nodeNeighborDirections[i][3] = 'b'; /* Node i + ab is one step below node i. */
}
for (i = 2 * a - 1; i <= a * b - a - 1; i += a)
{
nodeNeighbors[i][1] = 4;
nodeNeighbors[i][2] = i - a;
nodeNeighbors[i][3] = i - 1;
nodeNeighbors[i][4] = i + a;
nodeNeighbors[i][5] = i + a * b;
nodeNeighborDirections[i][0] = 'u'; /* Node i - a is one step up from node i. */
nodeNeighborDirections[i][1] = 'l'; /* Node i - 1 is one step left from node i. */
nodeNeighborDirections[i][2] = 'd'; /* Node i + a is one step down from node i. */
nodeNeighborDirections[i][3] = 'b'; /* Node i + ab is one step below node i. */
}
for (i = a * b * c - a * b + a; i <= a * b * c - 2 * a; i += a)
{
nodeNeighbors[i][1] = 4;
nodeNeighbors[i][2] = i - a * b;
nodeNeighbors[i][3] = i - a;
nodeNeighbors[i][4] = i + 1;
nodeNeighbors[i][5] = i + a;
nodeNeighborDirections[i][0] = 'a'; /* Node i - ab is one step above node i. */
nodeNeighborDirections[i][1] = 'u'; /* Node i - a is one step up from node i. */
nodeNeighborDirections[i][2] = 'r'; /* Node i + 1 is one step right from node i. */
nodeNeighborDirections[i][3] = 'd'; /* Node i + a is one step down from node i. */
}
for (i = a * b * c - a * b + 2 * a - 1; i <= a * b * c - a - 1; i += a)
{
nodeNeighbors[i][1] = 4;
nodeNeighbors[i][2] = i - a * b;
nodeNeighbors[i][3] = i - a;
nodeNeighbors[i][4] = i - 1;
nodeNeighbors[i][5] = i + a;
nodeNeighborDirections[i][0] = 'a'; /* Node i - ab is one step above node i. */
nodeNeighborDirections[i][1] = 'u'; /* Node i - a is one step up from node i. */
nodeNeighborDirections[i][2] = 'l'; /* Node i - 1 is one step left from node i. */
nodeNeighborDirections[i][3] = 'd'; /* Node i + a is one step down from node i. */
}
}
/* Lateral edges. */
if (c > 2)
{
for (i = a * b; i <= a * b * c - 2 * a * b; i += a * b)
{
nodeNeighbors[i][1] = 4;
nodeNeighbors[i][2] = i - a * b;
nodeNeighbors[i][3] = i + 1;
nodeNeighbors[i][4] = i + a;
nodeNeighbors[i][5] = i + a * b;
nodeNeighborDirections[i][0] = 'a'; /* Node i - ab is one step above node i. */
nodeNeighborDirections[i][1] = 'r'; /* Node i + 1 is one step right from node i. */
nodeNeighborDirections[i][2] = 'd'; /* Node i + a is one step down from node i. */
nodeNeighborDirections[i][3] = 'b'; /* Node i + ab is one step below node i. */
}
for (i = a * b + a - 1; i <= a * b * c - 2 * a * b + a - 1; i += a * b)
{
nodeNeighbors[i][1] = 4;
nodeNeighbors[i][2] = i - a * b;
nodeNeighbors[i][3] = i - 1;
nodeNeighbors[i][4] = i + a;
nodeNeighbors[i][5] = i + a * b;
nodeNeighborDirections[i][0] = 'a'; /* Node i - ab is one step above node i. */
nodeNeighborDirections[i][1] = 'l'; /* Node i - 1 is one step left from node i. */
nodeNeighborDirections[i][2] = 'd'; /* Node i + a is one step down from node i. */
nodeNeighborDirections[i][3] = 'b'; /* Node i + ab is one step below node i. */
}
for (i = 2 * a * b - a; i <= a * b * c - a * b - a; i += a * b)
{
nodeNeighbors[i][1] = 4;
nodeNeighbors[i][2] = i - a * b;
nodeNeighbors[i][3] = i - a;
nodeNeighbors[i][4] = i + 1;
nodeNeighbors[i][5] = i + a * b;
nodeNeighborDirections[i][0] = 'a'; /* Node i - ab is one step above node i. */
nodeNeighborDirections[i][1] = 'u'; /* Node i - a is one step up from node i. */
nodeNeighborDirections[i][2] = 'r'; /* Node i + 1 is one step right from node i. */
nodeNeighborDirections[i][3] = 'b'; /* Node i + ab is one step below node i. */
}
for (i = 2 * a * b - 1; i <= a * b * c - a * b - 1; i += a * b)
{
nodeNeighbors[i][1] = 4;
nodeNeighbors[i][2] = i - a * b;
nodeNeighbors[i][3] = i - a;
nodeNeighbors[i][4] = i - 1;
nodeNeighbors[i][5] = i + a * b;
nodeNeighborDirections[i][0] = 'a'; /* Node i - ab is one step above node i. */
nodeNeighborDirections[i][1] = 'u'; /* Node i - a is one step up from node i. */
nodeNeighborDirections[i][2] = 'l'; /* Node i - 1 is one step left from node i. */
nodeNeighborDirections[i][3] = 'b'; /* Node i + ab is one step below node i. */
}
}
/* Part Three */
/* Each lattice point that is on the inside of a face has 5 neighbors. */
if (a > 2 && b > 2)
{
/* Top face. */
for (i = 1; i <= b - 2; i++)
{
for (k = 1; k <= a - 2; k++)
{
n = i * a + k;
nodeNeighbors[n][1] = 5;
nodeNeighbors[n][2] = n - a;
nodeNeighbors[n][3] = n - 1;
nodeNeighbors[n][4] = n + 1;
nodeNeighbors[n][5] = n + a;
nodeNeighbors[n][6] = n + a * b;
nodeNeighborDirections[n][0] = 'u'; /* Node n - a is one step up from node n. */
nodeNeighborDirections[n][1] = 'l'; /* Node n - 1 is one step left from node n. */
nodeNeighborDirections[n][2] = 'r'; /* Node n + 1 is one step right from node n. */
nodeNeighborDirections[n][3] = 'd'; /* Node n + a is one step down from node n. */
nodeNeighborDirections[n][4] = 'b'; /* Node n + ab is one step below node n. */
}
}
/* Bottom face. */
for (i = 1; i <= b - 2; i++)
{
for (k = 1; k <= a - 2; k++)
{
n = i * a + k + a * b * (c - 1);
nodeNeighbors[n][1] = 5;
nodeNeighbors[n][2] = n - a * b;
nodeNeighbors[n][3] = n - a;
nodeNeighbors[n][4] = n - 1;
nodeNeighbors[n][5] = n + 1;
nodeNeighbors[n][6] = n + a;
nodeNeighborDirections[n][0] = 'a'; /* Node n - ab is one step above node n. */
nodeNeighborDirections[n][1] = 'u'; /* Node n - a is one step up from node n. */
nodeNeighborDirections[n][2] = 'l'; /* Node n - 1 is one step left from node n. */
nodeNeighborDirections[n][3] = 'r'; /* Node n + 1 is one step right from node n. */
nodeNeighborDirections[n][4] = 'd'; /* Node n + a is one step down node n. */
}
}
}
if (a > 2 && c > 2)
{
/* Front face. */
for (i = 1; i <= c - 2; i++)
{
for (k = 1; k <= a - 2; k++)
{
n = (i + 1) * a * b + k - a;
nodeNeighbors[n][1] = 5;
nodeNeighbors[n][2] = n - a * b;
nodeNeighbors[n][3] = n - a;
nodeNeighbors[n][4] = n - 1;
nodeNeighbors[n][5] = n + 1;
nodeNeighbors[n][6] = n + a * b;
nodeNeighborDirections[n][0] = 'a'; /* Node n - ab is one step above node n. */
nodeNeighborDirections[n][1] = 'u'; /* Node n - a is one step up from node n. */
nodeNeighborDirections[n][2] = 'l'; /* Node n - 1 is one step left from node n. */
nodeNeighborDirections[n][3] = 'r'; /* Node n + 1 is one step right from node n. */
nodeNeighborDirections[n][4] = 'b'; /* Node n + ab is one step below node n. */
}
}
/* Back face. */
for (i = 1; i <= c - 2; i++)
{
for (k = 1; k <= a - 2; k++)
{
n = i * a * b + k;
nodeNeighbors[n][1] = 5;
nodeNeighbors[n][2] = n - a * b;
nodeNeighbors[n][3] = n - 1;
nodeNeighbors[n][4] = n + 1;
nodeNeighbors[n][5] = n + a;
nodeNeighbors[n][6] = n + a * b;
nodeNeighborDirections[n][0] = 'a'; /* Node n - ab is one step above node n. */
nodeNeighborDirections[n][1] = 'l'; /* Node n - 1 is one step left from node n. */
nodeNeighborDirections[n][2] = 'r'; /* Node n + 1 is one step right from node n. */
nodeNeighborDirections[n][3] = 'd'; /* Node n + a is one step down from node n. */
nodeNeighborDirections[n][4] = 'b'; /* Node n + ab is one step below node n. */
}
}
}
if (b > 2 && c > 2)
{
/* Right face. */
for (i = 1; i <= c - 2; i++)
{
for (k = 1; k <= b - 2; k++)
{
n = i * a * b + a * k + a - 1;
nodeNeighbors[n][1] = 5;
nodeNeighbors[n][2] = n - a * b;
nodeNeighbors[n][3] = n - a;
nodeNeighbors[n][4] = n - 1;
nodeNeighbors[n][5] = n + a;
nodeNeighbors[n][6] = n + a * b;
nodeNeighborDirections[n][0] = 'a'; /* Node n - ab is one step above node n. */
nodeNeighborDirections[n][1] = 'u'; /* Node n - a is one step up from node n. */
nodeNeighborDirections[n][2] = 'l'; /* Node n - 1 is one step left from node n. */
nodeNeighborDirections[n][3] = 'd'; /* Node n + a is one step down from node n. */
nodeNeighborDirections[n][4] = 'b'; /* Node n + ab is one step below node n. */
}
}
/* Left face. */
for (i = 1; i <= c - 2; i++)
{
for (k = 1; k <= b - 2; k++)
{
n = i * a * b + k * a;
nodeNeighbors[n][1] = 5;
nodeNeighbors[n][2] = n - a * b;
nodeNeighbors[n][3] = n - a;
nodeNeighbors[n][4] = n + 1;
nodeNeighbors[n][5] = n + a;
nodeNeighbors[n][6] = n + a * b;
nodeNeighborDirections[n][0] = 'a'; /* Node n - ab is one step above node n. */
nodeNeighborDirections[n][1] = 'u'; /* Node n - a is one step up from node n. */
nodeNeighborDirections[n][2] = 'r'; /* Node n + 1 is one step right from node n. */
nodeNeighborDirections[n][3] = 'd'; /* Node n + a is one step down from node n. */
nodeNeighborDirections[n][4] = 'b'; /* Node n + ab is one step below node n. */
}
}
}
/* Part Four */
/* Every other node must be inside the cuboid and has 6 neighbors. */
for (i = 0; i < numberOfNodes; i++)
{
if (nodeNeighbors[i][1] == 0)
{
nodeNeighbors[i][1] = 6;
nodeNeighbors[i][2] = i - a * b;
nodeNeighbors[i][3] = i - a;
nodeNeighbors[i][4] = i - 1;
nodeNeighbors[i][5] = i + 1;
nodeNeighbors[i][6] = i + a;
nodeNeighbors[i][7] = i + a * b;
nodeNeighborDirections[i][0] = 'a'; /* Node i - ab is one step above node i. */
nodeNeighborDirections[i][1] = 'u'; /* Node i - a is one step up from node i. */
nodeNeighborDirections[i][2] = 'l'; /* Node i - 1 is one step left from node i. */
nodeNeighborDirections[i][3] = 'r'; /* Node i + 1 is one step right from node i. */
nodeNeighborDirections[i][4] = 'd'; /* Node i + a is one step down from node i. */
nodeNeighborDirections[i][5] = 'b'; /* Node i + ab is one step below node i. */
}
}
}
/* Change all zeroes at end of nodeNeighbors to -1...the rest of the program needs this??????? */
for (i = 0; i < numberOfNodes; i++)
{
for (j = nodeNeighbors[i][1] + 2; j < maxNeighborsPlus3; j++)
{
nodeNeighbors[i][j]= -1;
}
}
/* Get output requirements. */
cout << "Output all paths? [y / n] ";
cin >> outputAllPaths;
file << "Output all paths = " << outputAllPaths << endl;
if (outputAllPaths != 'y' && outputAllPaths != 'n')
goto error;
cout << "Output shape stats? [y / n] ";
cin >> outputShapeStats;
file << "Output shape stats = " << outputShapeStats << endl;
if (outputShapeStats != 'y' && outputShapeStats != 'n')
goto error;
/* Get starting node requirements. */
cout << "Run with all starting nodes? [y / n] ";
cin >> allStartNodes;
file << "Run with all starting nodes = " << allStartNodes << endl;
if (allStartNodes != 'y' && allStartNodes != 'n')
goto error;
if (allStartNodes == 'n')
{
/* Generate all CNSAPs starting with a user-specified first node and optionally, one or more second nodes. */
/* Initialise arrays holding node values to the invalid node number -1. */
for (i = 0; i < numberOfNodes; i++)
{
currentPath[i] = -1;
for (k = 1; k < maxNeighborsPlus3; k++)
{
unusableNodes[i][k] = -1;
unusedNodes[i][k] = -1;
}
}
/* Prompt user to enter the first node. */
cout << "Type in the first node number ";
cin >> firstNode;
file << "First node = " << firstNode << endl;
if (firstNode < 0 || firstNode > numberOfNodes - 1)
goto error;
currentNodePointer = 0;
currentPath[currentNodePointer] = firstNode; /* Puts the first node in the path. */
unusableNodes[currentNodePointer][1] = firstNode; /* Ensures that the first node cannot be used again in this path. */
/* Are one or more second nodes required? */
cout << "Do you want to enter one or more second nodes? [y / n] ";
cin >> specifySecondNodes;
file << "Second node requirement = " << specifySecondNodes << endl;
if (specifySecondNodes == 'y')
{
currentNodePointer++;
cout << "How many second nodes? ";
cin >> numberOfSecondNodes;
file << "Number of second nodes = " << numberOfSecondNodes << endl;
if (numberOfSecondNodes < 0 || numberOfSecondNodes > nodeNeighbors[firstNode][1])
goto error;
for (i = 1; i <= numberOfSecondNodes; i++)
{
cout << "Type in a second node number ";
cin >> secondNode;
file << "Second node = " << secondNode << endl;
matchCount = 0;
for (j = 1; j <= nodeNeighbors[firstNode][1]; j++)
{
if (secondNode != nodeNeighbors[firstNode][j + 1])
matchCount++;
}
if (matchCount == nodeNeighbors[firstNode][1])
goto error; /* Second node entered is not a neighbor of the first. */
if (i == 1)
{
/* Place the initial second node in the path and register all neighbors of the first node as unusable. */
currentPath[currentNodePointer] = secondNode;
for (j = 1; j <= nodeNeighbors[firstNode][1]; j++)
{
unusableNodes[currentNodePointer][j] = nodeNeighbors[firstNode][j + 1];
}
}
else
{
/* Check that this alternative second node has not already been specified. */
if (secondNode == currentPath[currentNodePointer])
goto error;
for (j = 1; j < i; j++)
{
if (secondNode == unusedNodes[currentNodePointer][j])
goto error;
}
/* As it has not already been specified, store it as an unused node for future use. */
unusedNodes[currentNodePointer][i - 1] = secondNode;
}
}
}
cout << endl;
file << endl;
/* Compute all the CNSAPs starting with the first and each of the second nodes specified. */
finished = false;
while (finished == false)
{
noNextNode = false;
while (noNextNode == false)
{
/* Point to the first neighbor. */
nextNeighborPointer = 2;
currentNode = currentPath[currentNodePointer];
do
{
candidateNextNode = nodeNeighbors[currentNode][nextNeighborPointer];
/* Now check to see if we can include this node in the path. */
addNode = true;
for (j = 0; j <= currentNodePointer; j++)
{
for (k = 1; k < maxNeighborsPlus3; k++)
{
if (candidateNextNode == unusableNodes[j][k])
{
addNode = false;
break;
}
}
if (addNode == false)
break;
}
nextNeighborPointer++;
}
while (addNode == false && candidateNextNode != -1);
/* To reach this point in the progam, we have either found a next node in the path or the path is complete. */
if (candidateNextNode == -1)
noNextNode = true;
if ((noNextNode == false) && (addNode == true))
{
currentNodePointer++;
currentPath[currentNodePointer] = candidateNextNode;
/* Since we've added the node to the path, make its usable neighbors unusable. */
nextUnusableNodePointer = 1;
for (i = 1; i <= nodeNeighbors[currentPath[currentNodePointer - 1]][1]; i++)
{
unusable = false;
for (j = 0; j < currentNodePointer; j++)
{
for (k = 1; k < maxNeighborsPlus3; k++)
{
if (unusableNodes[j][k] == -1)
break;
if (nodeNeighbors[currentPath[currentNodePointer - 1]][i + 1] == unusableNodes[j][k])
unusable = true;
}
}
if (unusable == false)
{
/* This node neighbor is not already unusable, so make it so. */
unusableNodes[currentNodePointer][nextUnusableNodePointer] = nodeNeighbors[currentPath[currentNodePointer - 1]][i + 1];
nextUnusableNodePointer++;
}
}
/* Record any unused unusable nodes in the current path as available for use in future paths. */
for (i = 2; i < maxNeighborsPlus3; i++)
{
unusedNodes[currentNodePointer][i - 1] = unusableNodes[currentNodePointer][i];
}
}
}
/* The path is complete because we didn't find a candidate for the next node. */
if (outputAllPaths == 'n')
{
if (currentNodePointer + 1 >= longestCNSAP)
{
cout << "Path = ";
file << "Path = ";
for (i = 0; i <= currentNodePointer; i++)
{
cout << " " << currentPath[i];
file << " " << currentPath[i];
}
cout << "; Length = " << currentNodePointer + 1 << endl;
file << "; Length = " << currentNodePointer + 1 << endl;
longestCNSAP = currentNodePointer + 1;
}
}
else
{
cout << "Path =";
file << "Path =";
for (i = 0; i <= currentNodePointer; i++)
{
cout << " " << currentPath[i];
file << " " << currentPath[i];
}
cout << "; Length = " << currentNodePointer + 1 << endl;
file << "; Length = " << currentNodePointer + 1 << endl;
}
/* Increment the number of paths of this length. */
pathLength = currentNodePointer + 1;
numberOfPathsPerLength[pathLength] = numberOfPathsPerLength[pathLength] + 1;
/* Determine minimum and maximum path lengths. */
minPathLength = min (minPathLength, pathLength);
maxPathLength = max (maxPathLength, pathLength);
/* Continue CNSAP construction until there are no unused nodes. */
anyUnusedNodes = true;
while (anyUnusedNodes == true)
{
if (unusedNodes[currentNodePointer][1] != -1)
{
anyUnusedNodes = false;
currentPath[currentNodePointer] = unusedNodes[currentNodePointer][1];
for (i = 1; i < maxNeighborsPlus3; i++)
{
unusedNodes[currentNodePointer][i] = unusedNodes[currentNodePointer][i + 1];
currentPath[currentNodePointer + i] = -1;
}
}
else
{
/* There are no more neighbors of the current node that we can branch to, so we have to wipe out these nodes from the unusableNodes array */
/* so that neighbors from the next current node can be inserted. */
for (i = 1; i < maxNeighborsPlus3; i++)
{
unusableNodes[currentNodePointer][i] = -1;
}
/* Backtrack to the previous node. */
currentNodePointer--;
}
if (currentNodePointer == 0)
{
finished = true;
anyUnusedNodes = false;
}
}
}
file << endl << "Column headings:" << endl;
file << " L = Path Length" << endl;
file << " N = Total number of paths with length L" << endl << endl;
file << "L N" << endl;
totalNumberOfPaths = 0;
for (i = minPathLength; i <= maxPathLength; i++)
{
file << i << " " << numberOfPathsPerLength[i] << " " << endl;
totalNumberOfPaths = totalNumberOfPaths + numberOfPathsPerLength[i];
}
file << "Total " << totalNumberOfPaths << " " << endl << endl;
}
else
{
/* Generate all paths starting with each node. */
file << endl;
for (m = 0; m < numberOfNodes; m++)
{
/* Initialise variables. */
for (i = 0; i < numberOfNodes; i++)
{
currentPath[i] = -1;
for (k = 1; k < maxNeighborsPlus3; k++)
{
unusableNodes[i][k] = -1;
unusedNodes[i][k] = -1;
}
}
currentNodePointer = 0;
currentPath[currentNodePointer] = m;
unusableNodes[currentNodePointer][1] = m;
/* The first node is set so compute all CNSAPs emanating from this node. */
finished = false;
while (finished == false)
{
noNextNode = false;
while (noNextNode == false)
{
nextNeighborPointer = 2;
currentNode = currentPath[currentNodePointer];
do
{
candidateNextNode = nodeNeighbors[currentNode][nextNeighborPointer];
/* Now check to see if we can move to this node. */
addNode = true;
for (j = 0; j <= currentNodePointer; j++)
{
for (k = 1; k < maxNeighborsPlus3; k++)
{
if (candidateNextNode == unusableNodes[j][k])
{
addNode = false;
break;
}
}
if (addNode == false)
break;
}
nextNeighborPointer++;
}
while (addNode == false && candidateNextNode != -1);
/* To reach this point in the progam, we have either found a next node in the path or the path is complete. */
if (candidateNextNode == -1)
noNextNode = true;
if ((noNextNode == false) && (addNode == true))
{
currentNodePointer++;
currentPath[currentNodePointer] = candidateNextNode;
currentPathDirections[currentNodePointer] = nodeNeighborDirections[currentNode][nextNeighborPointer - 3];
/* Since we've added a node to the path, make its usable neighbors unusable. */
nextUnusableNodePointer = 1;
for (i = 1; i <= nodeNeighbors[currentPath[currentNodePointer - 1]][1]; i++)
{
unusable = false;
for (j = 0; j < currentNodePointer; j++)
{
for (k = 1; k < maxNeighborsPlus3; k++)
{
if (nodeNeighbors[currentPath[currentNodePointer - 1]][i + 1] == unusableNodes[j][k])
unusable = true;
}
}
if (unusable == false)
{
unusableNodes[currentNodePointer][nextUnusableNodePointer] = nodeNeighbors[currentPath[currentNodePointer - 1]][i + 1];
nextUnusableNodePointer++;
}
}
/* Record any unused unusable nodes in the current path as available for use in future paths. */
for (i = 2; i < maxNeighborsPlus3; i++)
{
unusedNodes[currentNodePointer][i - 1] = unusableNodes[currentNodePointer][i];
}
}
}
/* The path is complete because we didn't find a candidateNextNode. */
if (outputShapeStats == 'n') goto skip_shapes;
/* Compute path shape stats. */
/* Rotate the directional representation of the path so that the starting direction is "up". */
if (latticeDimension == 2)
{
rotatedPathDirections[0] = ' ';
if (currentPathDirections[1] == 'd')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'd';
}
}
else if (currentPathDirections[1] == 'l')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'r';
}
}
else if (currentPathDirections[1] == 'r')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'l';
}
}
else if (currentPathDirections[1] == 'u')
{
for (i = 1; i <= currentNodePointer; i++)
{
rotatedPathDirections[i] = currentPathDirections[i];
}
}
rotatedPathDirections[currentNodePointer + 1] = '\0';
}
else if (latticeDimension == 3)
{
rotatedPathDirections[0] = ' ';
if (currentPathDirections[1] == 'a')
{
j = 2;
while (currentPathDirections[j] == 'a')
{
j++;
}
if (currentPathDirections[j] == 'd')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'l';
}
}
else if (currentPathDirections[j] == 'l')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'a';
}
}
else if (currentPathDirections[j] == 'r')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'b';
}
}
else if (currentPathDirections[j] == 'u')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'r';
}
}
}
else if (currentPathDirections[1] == 'b')
{
j = 2;
while (currentPathDirections[j] == 'b')
{
j++;
}
if (currentPathDirections[j] == 'd')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'l';
}
}
else if (currentPathDirections[j] == 'l')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'b';
}
}
else if (currentPathDirections[j] == 'r')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'a';
}
}
else if (currentPathDirections[j] == 'u')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'r';
}
}
}
else if (currentPathDirections[1] == 'd')
{
j = 2;
while (currentPathDirections[j] == 'd')
{
j++;
}
if (currentPathDirections[j] == 'a')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'd';
}
}
else if (currentPathDirections[j] == 'b')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'd';
}
}
else if (currentPathDirections[j] == 'l')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'd';
}
}
else if (currentPathDirections[j] == 'r')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'd';
}
}
}
else if (currentPathDirections[1] == 'l')
{
j = 2;
while (currentPathDirections[j] == 'l')
{
j++;
}
if (currentPathDirections[j] == 'a')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'b';
}
}
else if (currentPathDirections[j] == 'b')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'a';
}
}
else if (currentPathDirections[j] == 'd')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'l';
}
}
else if (currentPathDirections[j] == 'u')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'r';
}
}
}
else if (currentPathDirections[1] == 'r')
{
j = 2;
while (currentPathDirections[j] == 'r')
{
j++;
}
if (currentPathDirections[j] == 'a')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'a';
}
}
else if (currentPathDirections[j] == 'b')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'b';
}
}
else if (currentPathDirections[j] == 'd')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'l';
}
}
else if (currentPathDirections[j] == 'u')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'u';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'r';
}
}
}
else if (currentPathDirections[1] == 'u')
{
j = 2;
while (currentPathDirections[j] == 'u')
{
j++;
}
if (currentPathDirections[j] == 'a')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'u';
}
}
else if (currentPathDirections[j] == 'b')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'u';
}
}
else if (currentPathDirections[j] == 'l')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'u';
}
}
else if (currentPathDirections[j] == 'r')
{
for (i = 1; i <= currentNodePointer; i++)
{
if (currentPathDirections[i] == 'a')
rotatedPathDirections[i] = 'a';
if (currentPathDirections[i] == 'b')
rotatedPathDirections[i] = 'b';
if (currentPathDirections[i] == 'd')
rotatedPathDirections[i] = 'd';
if (currentPathDirections[i] == 'l')
rotatedPathDirections[i] = 'l';
if (currentPathDirections[i] == 'r')
rotatedPathDirections[i] = 'r';
if (currentPathDirections[i] == 'u')
rotatedPathDirections[i] = 'u';
}
}
}
rotatedPathDirections[currentNodePointer + 1] = '\0';
}
/* Increment the number of paths with this shape. */
if (totalNumberOfShapes == 0)
{
strcpy_s(distinctPathShapes[totalNumberOfShapes], rotatedPathDirections);
/*
numberOfPathsPerShape[totalNumberOfShapes] = 1;
*/
totalNumberOfShapes++;
}
else
{
shapeMatch = false;
for (i_ll = 0; i_ll <= totalNumberOfShapes; i_ll++)
{
if (strcmp(distinctPathShapes[i_ll], rotatedPathDirections) == 0)
{
shapeMatch = true;
/*
numberOfPathsPerShape[i_ll]++;
*/
break;
}
}
if (shapeMatch == false)
{
strcpy_s(distinctPathShapes[totalNumberOfShapes], rotatedPathDirections);
/*
numberOfPathsPerShape[totalNumberOfShapes] = 1;
*/
totalNumberOfShapes++;
}
}
skip_shapes:
/* Increment the number of paths of this length. */
pathLength = currentNodePointer + 1;
numberOfPathsPerLength[pathLength] = numberOfPathsPerLength[pathLength] + 1;
/* Increment the number of paths of this length for the starting node. */
startNodePerLength[currentPath[0]][pathLength] = startNodePerLength[currentPath[0]][pathLength] + 1;
/* Increment the number of paths of this length for the ending node. */
endNodePerLength[currentPath[currentNodePointer]][pathLength] = endNodePerLength[currentPath[currentNodePointer]][pathLength] + 1;
/* Increment the number of paths of this length for each node in the path. */
for (i = 0; i <= currentNodePointer; i++)
{
pathNodePerLength[currentPath[i]][pathLength] = pathNodePerLength[currentPath[i]][pathLength] + 1;
}
/* Determine minimum and maximum path lengths. */
minPathLength = min (minPathLength, pathLength);
maxPathLength = max (maxPathLength, pathLength);
/* Increment the number of paths for each starting-ending node pair. */
startEndNode[currentPath[0]][currentPath[currentNodePointer]] = startEndNode[currentPath[0]][currentPath[currentNodePointer]] + 1;
/* If appropriate, display the path. */
if (outputAllPaths == 'y' || (outputAllPaths == 'n' && currentNodePointer + 1 >= longestCNSAP))
{
longestCNSAP = pathLength;
cout << "Path =";
file << "Path =";
for (i = 0; i <= currentNodePointer; i++)
{
cout << " " << currentPath[i];
file << " " << currentPath[i];
}
cout << "; Length = " << pathLength << endl;
file << "; Length = " << pathLength << endl;
for (i = 1; i <= currentNodePointer; i++)
{
cout << " " << currentPathDirections[i];
file << " " << currentPathDirections[i];
}
cout << endl;
file << endl;
}
/* Construct new CNSAPs until all unused nodes are exhausted. */
anyUnusedNodes = true;
while (anyUnusedNodes == true)
{
if (unusedNodes[currentNodePointer][1] != -1)
{
anyUnusedNodes = false;
currentPath[currentNodePointer] = unusedNodes[currentNodePointer][1];
for (i = 1; i <= nodeNeighbors[currentPath[currentNodePointer - 1]][1]; i++)
{
if (currentPath[currentNodePointer] == nodeNeighbors[currentPath[currentNodePointer - 1]][i + 1])
{
currentPathDirections[currentNodePointer] = nodeNeighborDirections[currentPath[currentNodePointer - 1]][i - 1];
break;
}
}
for (i = 1; i < maxNeighborsPlus3; i++)
{
unusedNodes[currentNodePointer][i] = unusedNodes[currentNodePointer][i + 1];
currentPath[currentNodePointer + i] = -1;
}
}
else
{
/* There are no more neighbors of the current node that we can branch to, so we have to wipe out these nodes from the unusableNodes array */
/* so that neighbors from the next current node can be inserted. */
for (i = 1; i < maxNeighborsPlus3; i++)
{
unusableNodes[currentNodePointer][i] = -1;
}
/* Backtrack to the previous node. */
currentNodePointer--;
}
if (currentNodePointer == 0)
{
finished = true;
anyUnusedNodes = false;
}
}
}
}
if (outputShapeStats == 'y')
{
/* Display the number of paths of each length and shape. */
for (i_ll = 0; i_ll < totalNumberOfShapes; i_ll++)
{
pathLength = strlen(distinctPathShapes[i_ll]); /* Includes initial space to give number of nodes in path. */
numberOfShapesPerLength[pathLength] = numberOfShapesPerLength[pathLength] + 1;
}
file << endl << "Column headings:" << endl;
file << " L = Path Length" << endl;
file << " N = Total number of paths with length L" << endl;
file << " S = Number of different path shapes for each length" << endl << endl;
file << "L N S" << endl;
totalNumberOfPaths = 0;
for (i = minPathLength; i <= maxPathLength; i++)
{
file << i << " " << numberOfPathsPerLength[i] << " " << numberOfShapesPerLength[i] << endl;
totalNumberOfPaths = totalNumberOfPaths + numberOfPathsPerLength[i];
}
file << "Total " << totalNumberOfPaths << " " << totalNumberOfShapes << endl << endl;
/*
file << "Number of times each distinct path shape occurs" << endl;
file << "Shape No. Frequency Shape" << endl;
for (i = 0; i < totalNumberOfShapes; i++)
{
file << i << " " << numberOfPathsPerShape[i] << " " << distinctPathShapes[i] << endl;
}
file << endl;
*/
}
else
{
file << endl << "Column headings:" << endl;
file << " L = Path Length" << endl;
file << " N = Total number of paths with length L" << endl << endl;
file << "L N" << endl;
totalNumberOfPaths = 0;
for (i = minPathLength; i <= maxPathLength; i++)
{
file << i << " " << numberOfPathsPerLength[i] << " " << endl;
totalNumberOfPaths = totalNumberOfPaths + numberOfPathsPerLength[i];
}
file << "Total " << totalNumberOfPaths << " " << endl << endl;
}
file << "Number of times each node is the starting node (SN) in a path of each length (L)" << endl;
file << " SN ";
for (i = 0; i < numberOfNodes; i++)
{
file << i << " ";
}
file << endl;
file << " L" << endl;
for (j = minPathLength; j <= maxPathLength; j++)
{
file << j << " ";
for (i = 0; i < numberOfNodes; i++)
{
file << startNodePerLength[i][j] << " ";
startNode[i] = startNode[i] + startNodePerLength[i][j];
}
file << endl;
}
file << "Total ";
for (i = 0; i < numberOfNodes; i++)
{
file << startNode[i] << " ";
}
file << endl << endl;
file << "Number of times each node is the ending node (EN) in a path of each length (L)" << endl;
file << " EN ";
for (i = 0; i < numberOfNodes; i++)
{
file << i << " ";
}
file << endl;
file << " L" << endl;
for (j = minPathLength; j <= maxPathLength; j++)
{
file << j << " ";
for (i = 0; i < numberOfNodes; i++)
{
file << endNodePerLength[i][j] << " ";
endNode[i] = endNode[i] + endNodePerLength[i][j];
}
file << endl;
}
file << "Total ";
for (i = 0; i < numberOfNodes; i++)
{
file << endNode[i] << " ";
}
file << endl << endl;
file << "Number of times each node (N) is present in a path of each length (L)" << endl;
file << " N ";
for (i = 0; i < numberOfNodes; i++)
{
file << i << " ";
}
file << endl;
file << " L" << endl;
for (j = minPathLength; j <= maxPathLength; j++)
{
file << j << " ";
for (i = 0; i < numberOfNodes; i++)
{
file << pathNodePerLength[i][j] << " ";
pathNode[i] = pathNode[i] + pathNodePerLength[i][j];
}
file << endl;
}
file << "Total ";
for (i = 0; i < numberOfNodes; i++)
{
file << pathNode[i] << " ";
}
file << endl << endl;
file << "Number of paths for each starting node (SN) and ending node (EN) pair" << endl;
file << " SN ";
for (i = 0; i < numberOfNodes; i++)
{
file << i << " ";
}
file << endl;
file << "EN" << endl;
for (j = 0; j < numberOfNodes; j++)
{
file << j << " ";
for (i = 0; i < numberOfNodes; i++)
{
file << startEndNode[i][j] << " ";
}
file << endl;
}
}
cout << endl << "The program is done" << endl;
file << endl << "The program is done" << endl;
goto done;
error:
cout << endl << "Input error: Program terminated" << endl;
file << endl << "Input error: Program terminated" << endl;
done:
file.close();
return 0;
}
